
class QNode {
    val: boolean
    isLeaf: boolean
    topLeft: QNode | null
    topRight: QNode | null
    bottomLeft: QNode | null
    bottomRight: QNode | null
    constructor(val?: boolean, isLeaf?: boolean, topLeft?: QNode, topRight?: QNode, bottomLeft?: QNode, bottomRight?: QNode) {
        this.val = (val===undefined ? false : val)
        this.isLeaf = (isLeaf===undefined ? false : isLeaf)
        this.topLeft = (topLeft===undefined ? null : topLeft)
        this.topRight = (topRight===undefined ? null : topRight)
        this.bottomLeft = (bottomLeft===undefined ? null : bottomLeft)
        this.bottomRight = (bottomRight===undefined ? null : bottomRight)
    }
}

function construct(grid: number[][]): QNode | null {
  function build(t: number, b: number, l: number, r: number): QNode | null {
    const sign = grid[t][l];
    const s = r - l;
    if(s === 1) {
      return new QNode(sign === 1, true);
    }
    for(let i = t; i < b; i++) {
      for(let j = l; j < r; j++) {
        if(grid[i][j] !== sign) {
          return new QNode(true, 
            false, 
            build(t, b - s / 2, l, r - s / 2), 
            build(t, b - s / 2, l + s / 2, r), 
            build(t + s / 2, b, l, r - s / 2), 
            build(t + s / 2, b, l + s / 2, r));
        }
      }
    }
    return new QNode(sign === 1, true);
  }
  const len = grid.length;
  return build(0, len, 0, len);
};